//值域打家劫舍，记忆化搜索
class Solution {
public:
    //不选power[i]：从PowerCnt[0]~PowerCnt[i-1]中选择可以得到的伤害最大值
    //  选power[i]：从PowerCnt[0]~PowerCnt[j-1]中选择可以得到的伤害最大值 其中j是满足power[j]<=a[i]-2的最大值
    long long dfs(vector<pair<int, int>> &PowerCnt, vector<long long> &memo, int i) 
    {
        if(i<0) return 0;

        long long& res=memo[i];
        if(res!=-1) return res; //已被计算

        auto &[power, cnt]=PowerCnt[i];
        int j=i;
        while(j&&PowerCnt[j-1].first>=power-2) j--; //j是最小的满足power[j]>=a[i]-2的数
        return res=max(dfs(PowerCnt, memo, i-1), dfs(PowerCnt, memo, j-1)+1ll*power*cnt);
    }

    long long maximumTotalDamage(vector<int>& power) {
        map<int, int> cnt; //每个值出现的次数
        for(int x:power) cnt[x]++;

        vector<pair<int, int>> PowerCnt(cnt.begin(), cnt.end());
        ranges::sort(PowerCnt);
        int n=PowerCnt.size();

        vector<long long> memo(n, -1); //未被计算
        return dfs(PowerCnt, memo, n-1);
    }
};